/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 17655
 * Date: 2025-01-07
 * Time: 21:11
 */
public class test2 {
    /**
    归并排序   稳定    nlogn
     */
    public int[] sortArray(int[] nums) {
        tmp = new int[nums.length];
        mergeSort(nums,0,nums.length-1);
        return nums;
    }

    // 优化：将tmp变成全局变量
    int[] tmp;

    public void mergeSort(int[] nums,int left,int right){
        if(left>=right){
            return;
        }
        // 1.根据中间点划分区间
        int mid = left + (right-left)/2;
        // 2.把左右区间排序
        // [left,mid] [mid+1,right]
        mergeSort(nums,left,mid);
        mergeSort(nums,mid+1,right);

        // 3.合并两个有序数组
        tmp = new int[right-left+1];
        int cur1 = left;
        int cur2 = mid+1;
        int i=0;
        while(cur1<=mid && cur2<=right){
            tmp[i++] = nums[cur1]<=nums[cur2]?nums[cur1++]:nums[cur2++];
        }
        // 处理未遍历完的数组
        while(cur1<=mid){
            tmp[i++] = nums[cur1++];
        }
        while(cur2<=right){
            tmp[i++] = nums[cur2++];
        }
        // 4.还原数组
        for(int j=left;j<=right;j++){
            nums[j] = tmp[j-left];
        }
    }
}
